package leetcode.weekly.week325;

import java.util.TreeSet;

//Solution3Test
public class Solution3 {

	public int maximumTastiness(int[] price, int k) {
		TreeSet<Integer> ts = new TreeSet<>();
		for (int p : price) {
			ts.add(p);
		}
		int ans = 0;
		int l = 0, r = (int) 1e9 + 1;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			int p = ts.first();
			int cnt = k - 1;
			boolean ok = true;
			while (cnt > 0) {
				Integer cur = ts.ceiling(p + m);
				if (cur == null) {
					ok = false;
					break;
				}
				p = cur;
				cnt--;
			}
			if (ok) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans;
	}
}
